#pragma once
#include "Node.h"
#include <string>
#include <iostream>
#include <sstream>

using namespace std;
/** \brief Contains all functions for the linked list, namely adding and removing items, searching in the list etc.
*
*/

template <class INFO>
class List
{
	class Iterator
	{
	public:
		typedef Iterator self_type;
		typedef Node<INFO> value_type;
		typedef Node<INFO> &reference;
		typedef Node<INFO>* pointer;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		Iterator(pointer ptr) : ptr_(ptr) { } //Constructor
		self_type operator++() { self_type i = *this; ptr_ = ptr_->next; return i; }
		self_type operator++(int junk) { ptr_ = ptr_->next; return *this; }
		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }
		bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }

	private:
		pointer ptr_;
	};

protected:

	Node<INFO> *head;
	Node<INFO> *tail;

public:

	List()
	{
		head = tail = nullptr;
	}

	List(const List &list)
	{
		Node<INFO> *n = list.head;
		while (n != nullptr)
		{
			this->add_at_head(n->info);
			n = n->next;
		}

	}

	void add_at_head(INFO info)
	{
		if (head == nullptr)
		{
			head = new Node<INFO>(info);
			tail = head;
		}
		else
		{
			Node<INFO> *n = new Node<INFO>(info);
			n->next = head;
			head = n;
		}
	}

	Node<INFO> *search(INFO &info)
	{
		Node<INFO> *n = head;
		if (n == nullptr)
			return nullptr;
		else
		{
			do
			{
				if (n->info == info)
					return n;
				n = n->next;
			} while (n != nullptr);
		}
		return nullptr;
	}

	void clear()
	{
		Node<INFO> *n = head;
		Node<INFO> *d;
		while (n != nullptr)
		{
			d = n;
			n = n->next;
			delete d;
		}
		head = tail = nullptr;
	}

	void remove(Node<INFO> *d)
	{
		Node<INFO> *b;
		if (d == nullptr || head == nullptr)
			return;
		else if (d == head && head == tail)
		{
			delete d;
			head = tail = nullptr;
		}
		else if (d == head)
		{
			head = head->next;
			delete d;
		}
		else if (d == tail)
		{
			b = nodeBefore(d);
			b->next = nullptr;
			tail = b;
			delete d;
		}
		else
		{
			b = nodeBefore(d);
			b->next = d->next;
			delete d;
		}

	}

	string str()
	{
		ostringstream oss;

		Node<INFO> *n = head;
		if (n == nullptr)
			return "";
		else
		{
			do
			{
				oss << n->info << " ";
				n = n->next;
			} while (n != nullptr);
		}
		return oss.str();
	}

	Node<INFO> *nodeBefore(Node<INFO> *d)
	{
		Node<INFO> *s = head;
		while (s != nullptr)
		{
			if (s->next == d)
			{
				return s;
			}
			else
				s = s->next;
		}
	}

	Iterator begin()
	{
		return Iterator(head);
	}

	Iterator end()
	{
		return Iterator(nullptr);
	}

	void split_odd_even(List<INFO> &odd, List<INFO> &even)
	{
		Node<INFO> *n = this->head;
		while (n != nullptr)
		{
			if (n->info % 2 == 0)
			{
				even.add_at_head(n->info);
			}
			else
			{
				odd.add_at_head(n->info);
			}
			n = n->next;
		}
	}

	List &operator=(const List<INFO> &list)
	{
		Node<INFO> *n = list.head;
		while (n != nullptr)
		{
			this->add_at_head(n->info);
			n = n->next;
		}
		return *this;
	}

	~List()
	{
		Node<INFO> *n = head;
		Node<INFO> *d;
		while (n != nullptr)
		{
			d = n;
			n = n->next;
			delete d;
		}
	}
};

